// https://www.lintcode.com/problem/reverse-pairs/description?_from=ladder&&fromId=6
// 判断逆序数，归并排序的思路，左边逆序数+右边逆序数+左右合并逆序数

class Solution {
private:
    int * tmp;
public:
    /**
     * @param A: an array
     * @return: total of reverse pairs
     */
     
    // Time Limit Exceeded
    // long long reversePairs(vector<int> &A) {
    //     long long cnt = 0;
    //     for (int i = 0; i < A.size(); ++i)
    //     {
    //         for (int j = i + 1; j < A.size(); ++j)
    //         {
    //             if (A[i] > A[j]) cnt++;
    //         }
    //     }
    //     return cnt;
    // }
    
    
    
    // 归并排序
    long long merge(vector<int> &A, int l, int m, int r)
    {
        long long ans = 0;
        // int i = l, j = m;
        int i = l, j = m + 1, k = l;
        // while (i < m && j < r)
        while (i <= m && j <= r)
        {
            if (A[i] > A[j]) 
            {
                // tmp.push_back(A[j++]);
                tmp[k++] = A[j++];
                ans += m - i + 1;
            }
            else tmp[k++] = A[i++];
        }
        // while (i < m) tmp.push_back(A[i++]);
        // while (j < r) tmp.push_back(A[j++]);
        while (i <= m) tmp[k++] = A[i++];
        while (j <= r) tmp[k++] = A[j++];
        // A = tmp;       // 错误，注意排序的只是A的一部分!
        for (int i = l; i <= r; ++i)
        {
            A[i] = tmp[i];
        }
        return ans;
    }
    long long mergeSort(vector<int> &A, int l, int r)
    {
        long long ans = 0;
        // vector<int> tmp(A.size(), 0); TLE
        // int *tmp = new int[A.size()]; MLE
        if (l >= r) return ans;
        int mid = (r - l) / 2 + l;
        ans += mergeSort(A, l, mid);
        ans += mergeSort(A, mid + 1, r);
        ans += merge(A, l, mid, r);
        return ans;
    }
    long long reversePairs(vector<int> &A) {
        tmp = new int[A.size()];
        return mergeSort(A, 0, A.size() - 1);
    }
};